﻿using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//复杂度分析，和二叉树的高度有关系
//时间复杂度：最坏，树全部为左孩子，树高为n，每一层比较一次O（n），趟数=树高=n,排序O(n2)
//          ：最好，树左右均匀，树高为logn，每一层比较一次O（n），趟数=树高=logn,排序O(nlogn)
//空间复杂度：递归使用栈，和递归次数也就是树高有关系
//             最好logn，最坏n
//稳定性：不稳定

class SolQuickQort
{

    public void swap(int[] nums, int x, int y)
    {
        int swap = nums[x];
        nums[x] = nums[y];
        nums[y] = swap;
    }

    public void Sort(int[] nums,int  left,int right)//这个快排算法应该是生效的，但是需要额外维护一个边界值，应该想办法让栈自动维护
    {
        int val = nums[left];//基准值
        //记录一下左右边界
        int originL = left;
        int originR = right;
        while (left < right)
        {
            //先移动右边的
            while (left < right && nums[right] >= val)
            {
                right--;
            }
            swap(nums, left, right);

            while (left < right && nums[left] <= val)
            {
                left++;

            }
           
                swap(nums, left, right);
           
                
        }
        if(originL< left)
        {
            Sort(nums, originL, left - 1);//左半
        }
        if (right < originR)
        {
            Sort(nums, right + 1, originR);//右半
        }


    }


    public void QuickSort(int[] nums, int left, int right)
    {
        if(left < right)//递归终止的条件，返回上一层
        {
            //排序一次
           int pivotIndex= Partition(nums, left, right);
            QuickSort(nums, left, pivotIndex-1);//这里的left没变
            QuickSort(nums, pivotIndex+1, right);   

        }
    }

    private int Partition(int[] nums, int left, int right)
    {
        int val = nums[left];//基准值
        while (left < right)
        {
            //先移动右边的
            while (left < right&&nums[right] >= val)
            {
                right--;
            }

            swap(nums, left, right);
            while (left < right && nums[left] <= val)
            {
                left++;

            }

            swap(nums, left, right);//这两个数字一样，并且等于val的时候，会死循环
        }
        return left;//返回left和right一样，right=left=pivot分界线
    }
}

class ProgratQuick
{

    static void MainQuickSort()
    {

        int[] nums = { 53, 17, 78, 09, 45, 65, 87, 32 };
        //int[] nums = { 2, 0, 2, 1, 1, 0 };//有一些bug，重复数字出问题
        //int[] nums = { 2, 1, 3, 4, 5 };
        int len = nums.Length;

        //int valIndex=0;
        int left = 0;
       

        int right = len - 1;
        SolQuickQort solQuickQort = new SolQuickQort();
        solQuickQort.Sort(nums, left, right);
        //solQuickQort.QuickSort(nums, left, right);
        for (int i = 0; i < len; i++)
        {
            Console.WriteLine(nums[i]);
        }
        Console.ReadKey();


    }
}
